//lc239题，最大滑动窗口-取窗口中的最大值
/*
使用单调队列解决问题，即创建一个辅助队列，将单调（从左到右递减）的元素维持在队列中，让最有可能成为最大值的元素尽可能靠左（队列的front端）
单调队列即是维护元素单调递减或者单调递增
具体实现方法Push(),Pop(),getMax()
使用deque双向队列实现，可以从front和back端分别进行插入弹出
Push(int val):将进入窗口的数压入队列，若队列的back端有数比val小，则弹出该数直到val是队列里的最小值
Pop(int val)：当窗口左端为val并准备移动时，判断val是否等于队列的front，是则弹出（该最大值已经被窗口踢出），不是则无必要操作
getMax():由于是单调队列，那么front即是最大（小）的元素
*/

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

//单调队列的实现
class Moqueue_down  //从左到右递减的队列
{
public:
    deque<int> mque;
    void Pop(int val)
    {
        if(!mque.empty()&&val==mque.front())
            mque.pop_front();
    }

    void Push(int val)
    {
        while(!mque.empty()&&val>mque.back())
            mque.pop_back();    //实现back总是最小
        mque.push_back(val);
    }
    int getMax()
    {
        return mque.front();
    }
};

//从左到右递增的队列（最小值在左边fornt）
//其实区别只有在Push方法的判断中
class Moqueue_up
{
public:
    deque<int>mque;
    void Pop(int val)   //这个只跟窗口移动方向有关
    {
        if(!mque.empty()&&val==mque.front())
            mque.pop_front();
    }
    void Push(int val)
    {
        while(!mque.empty()&&val<mque.back())
            mque.pop_back();
        mque.push_back(val);
    }
    int getMin()    //最小值在front
    {
        return mque.front();
    }
};



//题解
vector<int> maxSlidingWindow(vector<int>& nums,int k)
{   
    Moqueue_down mque;
    //先处理前k个
    for(int i=0;i<k;i++)
    {
        mque.Push(nums[i]);
    }
    vector<int> result;
    result.push_back(mque.getMax());
    for(int i=k;i<nums.size();i++)
    {
        mque.Pop(nums[i-k]);
        mque.Push(nums[i]);
        result.push_back(mque.getMax());
    }

    return result;

}





//附：deque的方法

/*


push_back()//在队列的尾部插入元素。
emplace_front()//与push_front()的作用一样 
push_front()//在队列的头部插入元素。
emplace_back()//与push_back()的作用一样 
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素。
back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器
rbegin()//返回逆头位置的迭代器 
rend()//返回逆尾-1位置的迭代器 
insert()//在指定位置插入元素 
erase()//在指定位置删除元素 



*/